The present invention generally relates to map display systems, map data processing apparatuses, map display apparatuses, and map display methods for general navigation systems, such as car navigation systems and pedestrian navigation systems for showing pedestrians routes to their destinations. More particularly, the present invention relates to a map display system, a map data processing apparatus, a map display apparatus, and a map display method having a function to display a three-dimensional map.
In recent years, technologies for displaying three-dimensional maps for car navigation systems have been developed, and three-dimensional maps have become displayable on car navigation screens. Thus, with car navigation systems, users can know, in terms of three dimensions, relationships of the current position and three-dimensional structures, such as surrounding buildings and three-dimensional intersections.
Also, global positioning systems (GPSs) for knowing the current position have been installed or optionally installed on terminals, such as personal digital assistants (PDAs) and cellular telephones. Thus, pedestrian navigation systems for guiding users who carry such terminals to their destinations from the current position have been put into practical use.
Furthermore, three-dimensional graphics rendering engines capable of rendering three-dimensional graphics on the screen of such portable terminals in real time at high speed by hardware have recently been put into practical use, and graphics have been able to be rendered at high speed even with portable terminals.
Hard disks have also been installed on car navigation apparatuses. Also, external mass memories, such as the Memory Stick (Memory Stick is a registered trademark of Sony Corporation), can be installed on portable terminals, such as PDAs. Large volumes of data, such as three-dimensional map data, are stored in such memories, so that the data can be accessed at high speed.
Scene graphs, which are one type of technology for displaying three-dimensional graphics, are used for rendering objects having a complicated structure.
FIGS. 33A and 33B show an example of an object structured using a scene graph. FIG. 33A shows a three-dimensional robot 140 as the object, and FIG. 33B shows parts constituting the object.
FIG. 34 shows an example of the scene graph representing the structure of the object shown in FIG. 33A.
FIG. 35 shows an arrangement of the parts constituting the object represented using the scene graph.
For example, in order to represent the robot 140 shown in FIG. 33A, a part 141 serving as a head or body, a part 142 serving as an arm, and a part 143 serving as a leg are defined in advance, and part IDs, such as “1”, “2”, and “3”, are allocated to the parts 141, 142, and 143, respectively, to be managed, as shown in FIG. 33B. Positional relationships of such parts are described from a root such that each of the parts is converted in terms of scaling, rotation, and translation in that order, as defined in the scene graph in FIG. 34.
Accordingly, for example, a head 141a, a body 141b, a left arm 142a, a right arm 142b, a left leg 143a, and a right leg 143b of the robot are represented, as shown in FIG. 35, and are rendered.
In general, a plurality of formats for describing scene graphs and a plurality of application program interfaces (APIs) for managing the scene graphs are available. A virtual reality modeling language (VRML) and XSI (trademark) files by Softimage Inc. are typical formats. Java 3D (registered trademark) and OpenInventor (trademark) are known as APIs capable of managing the scene graphs.
A data holding method capable of facilitating searching using a k-dimensional tree structure (more specifically, a 6-dimensional tree structure) in a scene graph defining a three-dimensional building is disclosed, for example, in Japanese Unexamined Patent Application Publication No. 10-293862 (FIG. 14).
In contrast, level of detail (LOD) technologies for realizing high-speed rendering without degrading the outline of three-dimensional objects, to be as accurate as possible, have been available.
FIGS. 36 to 38 explain an example of an LOD technology.
For example, as shown in FIG. 36, according to the LOD technology, an object to be rendered is prepared in advance for a plurality of levels of details, such as an object 150 at level 1, an object 151 at level 2, and an object 152 at level 3. For rendering, an object at the most appropriate level of detail is selected in accordance with a distance from a view point (position of a camera 155).
For example, for an object very close to the camera 155, the object 150 at level 1 is rendered. For an object farther away from the camera 155, the object 151 at level 2 is rendered. For an object much farther away from the camera 155, the object 152 at level 3 is rendered. Accordingly, as compared with normal technologies in which complete data must be rendered for any object at any location, rendering of simplified data for an object located far away from a camera and rendering of detailed data for an object located near the camera can be achieved by introduction of the LOD technology, as shown in FIG. 38. Thus, since a load of a graphics rendering engine can be reduced without degrading the outline of a three-dimensional object, the rendering speed can be increased.
In order to avoid frame dropping when three-dimensional data is sent and rendered in real time during communication, a method for avoiding frame dropping in frame rate by categorizing an object depending on the level of detail using an LOD technology and by postponing rendering of a detailed portion is disclosed in Japanese Unexamined Patent Application Publication No. 2002-279449 (Paragraph Nos. 0072 to 0077).
There are many types of LOD technologies, and a quadtree structure is widely used as a technique appropriate for object data having a structure similar to that of a three-dimensional map.
According to this technique, three-dimensional data widely spreading over a particular plane, such as a three-dimensional map, is recorded by being categorized into nodes at a plurality of hierarchical levels depending on the level of detail of the object, and each of the nodes is divided into four nodes at each of the hierarchical levels.
FIGS. 39 to 41 explain a quadtree structure.
In FIG. 39, original data 160 is categorized into nodes at three hierarchical levels, such as level 1 for a node 161 having a large object; level 2 for nodes 162 having a medium-sized object; and level 3 for nodes 163 having a small object, and each of the nodes is divided into four nodes at each of the hierarchical levels. Accordingly, LOD can be realized by performing rendering of each node such that a node at a high level of detail is rendered for an object near a view point and a node at a low level of detail is rendered for an object far away from the view point.
For example, as shown in FIG. 40, if a distance from a camera 170 exceeds a threshold (FAR PLANE) 171, rendering is not performed. If a distance from the camera 170 is between the threshold 171 and a threshold 172, a map of a node only at the lowest level of detail is rendered. If a distance from the camera 170 is between the threshold 172 and a threshold 173, a map of a node at the second-lowest level of detail is rendered. If a distance from the camera 170 is between the threshold 173 and a threshold 174, a map of a node at the third-lowest level of detail is rendered. If a distance from the camera 170 is between the threshold 174 and a threshold (NEAR PLANE) 175, a map of a node at the highest level of detail is rendered. If a distance from the camera 170 is less than the threshold 175, rendering is not performed.
FIG. 41 shows how an LOD quadtree structure is realized. First, assuming that a square 180 that covers the whole data space structured in a two-dimensional wide plane, such as a ground surface, exists, the square 180 is divided into four equally divided surfaces 180a, 180b, 180c, and 180d. Components 181 and 182, which extend over a plurality of divided surfaces, are regarded as widely-extended and huge components. Thus, the components 181 and 182 are stored in a node 190 at a higher hierarchical level. Nodes 191a, 191b, 191c, and 191d corresponding to the respective divided surfaces 180a, 180b, 180c, and 181d are provided as child nodes at a lower hierarchical level, and other components are attributed to the corresponding child nodes.
By repeating such processing as necessary, the map can be hierarchically structured depending on the level of detail.
More specifically, when this method is applied to a three-dimensional map, the map can be automatically hierarchically structured (although an object that is on the boundary for defining hierarchical levels is exceptional), such as a node at the highest hierarchical level for storing mountains, seas, roads, which extend over a wide area; nodes at a lower hierarchical level for storing large structures, such as buildings; and nodes at the lowest hierarchical level for storing houses, signal lights, traffic signs, and the like.
Accordingly, the three-dimensional map can be effectively rendered using an LOD technology.
For various three-dimensional navigation systems, typified by three-dimensional car navigation systems, which have recently become commonplace, three-dimensional maps must be rendered in real time at high speed and with high accuracy. However, representing three-dimensional maps using known scene graphs need enormous volumes of data to be processed, thus making it difficult to perform high-speed processing.
Also, in a known quadtree structure, a high-rise building functioning as a landmark is likely to be categorized into a node for small objects. Thus, a high-rise building located far away from a view point is likely to be omitted even if it is actually viewable. In order to avoid this, processing, such as rendering a node that includes a high-rise building, is needed. However, such processing for determining whether or not a node includes a high-rise building reduces the rendering speed and degrades the significance of data omission.
Also, not only high-speed rendering but displaying point of interest (POI) information appropriate for a landmark, such as a building on a map designated by a user, is also needed.